package com.leetcode.algorithm.y22.m07;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 733. 图像渲染
 * 
 * https://leetcode.cn/problems/flood-fill/
 * 
 * @author jie.deng
 *
 */
class Question0733Solution01 {

	public int[][] floodFill(int[][] image, int sr, int sc, int color) {
		int oldColor = image[sr][sc];
		if (oldColor == color) {
			return image;
		}
		int rows = image.length;
		int cols = image[0].length;

		Set<Integer> visitedSet = new HashSet<>();
		Queue<Integer> queue = new LinkedList<>();

		int idx = getIdx(sr, sc, cols);
		visitedSet.add(idx);
		queue.offer(idx);
		while (!queue.isEmpty()) {
			for (int i = 0; i < queue.size(); i++) {
				idx = queue.poll().intValue();
				int row = idx / cols;
				int col = idx % cols;
				image[row][col] = color;
				// 上
				if (row >= 1) {
					idx = getIdx(row - 1, col, cols);
					if (image[row - 1][col] == oldColor && visitedSet.add(idx)) {
						queue.offer(idx);
					}
				}
				// 下
				if (row < rows - 1) {
					idx = getIdx(row + 1, col, cols);
					if (image[row + 1][col] == oldColor && visitedSet.add(idx)) {
						queue.offer(idx);
					}
				}
				// 左
				if (col >= 1) {
					idx = getIdx(row, col - 1, cols);
					if (image[row][col - 1] == oldColor && visitedSet.add(idx)) {
						queue.offer(idx);
					}
				}
				// 下
				if (col < cols - 1) {
					idx = getIdx(row, col + 1, cols);
					if (image[row][col + 1] == oldColor && visitedSet.add(idx)) {
						queue.offer(idx);
					}
				}
			}
		}
		return image;
	}

	private int getIdx(int row, int col, int cols) {
		return row * cols + col;
	}

}